class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        len_t = len(t)
        len_s = len(s)
        if not t or len_t > len_s:
            return 0

        cnt = 0
        ch = t[0]
        for i in range(len_s):
            if s[i] == ch:
                if len_t == 1:
                    cnt += 1
                else:
                    cnt += self.numDistinct(s[i+1:], t[1:])
            if len_s - i < len_t:
                break

        return cnt


# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    ret = Solution().numDistinct('rrabbbit', 'rabit')
    print(ret)